#ifndef GENERIK_TREE_H
#define GENERIK_TREE_H

/** \file gtree.h
Defines a generik tree class, which can act both as a container
and as a base class for tree-like specialisation.
*/

#include <list>
#include <stdexcept>

namespace generik
{

	/** basic iterator template
	This class implements a basic iterator on a TREE-like node.
	It has the usual iterator paradigms, such as incrementation and deferencing operators.
	It also acts as a controller of the node, by adding tree-building and -modification
	operators.
	Because a tree has more than one levels, operators to ascend and descend the tree
	are also provided.
	*/
	template <typename TREE>
	struct basic_iterator
	{
		TREE* _tree;
	
		basic_iterator()
		: _tree(0)
		{}
	
		explicit basic_iterator(TREE* tree_in)
		: _tree(tree_in)
		{}
	
		basic_iterator(const basic_iterator& iter)
		: _tree(iter._tree)
		{}
	
		bool operator!=(const basic_iterator& iter) const
		{
			return iter._tree != _tree;
		}
	
		basic_iterator& operator++()
		{
			_tree = _tree->_next;
		}
	
		TREE& operator*() const
		{
			return *_tree;
		}
	
		TREE& operator->() const
		{
			return *_tree;
		}
	
		basic_iterator& up()
		{
			_tree = _tree->_parent;
			return *this;
		}
		basic_iterator& down()
		{
			_tree = _tree->_child;
			return *this;
		}
	
		basic_iterator& push_front(TREE* t) const
		{
			_tree->push_front(t);
			return _tree->_child;
		}
		basic_iterator& push_back(TREE* t) const
		{
			_tree->push_back(t);
			return _tree->_end;
		}
	};

	/** basic const iterator template
	This class implements a basic const iterator on a TREE-like node.
	It provides the const set of functionality as provided by the basic_iterator,
	but makes sure the node pointed to is const.
	*/
	template <typename TREE>
	struct basic_const_iterator
	{
		const TREE* _tree;
	
		basic_const_iterator()
		: _tree(0)
		{}
	
		basic_const_iterator(const basic_iterator<TREE>& iter)
		: _tree(iter._tree)
		{}
	
		explicit basic_const_iterator(const TREE* tree_in)
		: _tree(tree_in)
		{}
	
		basic_const_iterator(const basic_const_iterator& iter)
		: _tree(iter._tree)
		{}
	
		bool operator!=(const basic_const_iterator& iter) const
		{
			return iter._tree != _tree;
		}
	
		basic_const_iterator& operator++()
		{
			_tree = _tree->_next;
		}
	
		const TREE& operator*() const
		{
			return *_tree;
		}
		const TREE& operator->() const
		{
			return *_tree;
		}
	
		basic_const_iterator& up()
		{
			_tree = _tree->_parent;
			return *this;
		}
		basic_const_iterator& down()
		{
			_tree = _tree->_child;
			return *this;
		}
	};
	
	/** basic tree template
	This class implements a tree-like node. It has the usual parent, child and prev/next
	pointers. 
	
	\note The catch is in the way these are declared.
	Usually, they would be declared to point to the same type as the tree object itself.
	In this case, however, the type they point to is templatised.
	This allows us to derive from this template, and provide our class as template 
	parameter. Since the class is always used as a pointer in this basic tree template, 
	recursion does not take place, but we are always assured that stored pointers are
	of our type.
	*/
	template <typename TREE>
	struct basic_tree
	{
		TREE *_parent, *_next, *_prev, *_child, *_end;
	
		basic_tree()
		: _parent(0)
		, _next(0), _prev(0)
		, _child(0), _end(0)
		{}
	
		bool empty() const
		{
			return _child == 0;
		}
	
		unsigned int size() const
		{
			unsigned int result = 0;
			TREE* c = _child;
			while (c)
			{
				++result;
				c = c->_next;
			}
			return result;
		}
	
		TREE& child()
		{
			if (_child) return *child;
			throw std::range_error();
		}
		const TREE& child() const
		{
			if (_child) return *child;
			throw std::range_error();
		}
	
		TREE& last()
		{
			TREE* t = _end;
			if (t) return *t;
			throw std::range_error();
		}
		const TREE& last() const
		{
			TREE* t = _end;
			if (t) return *t;
			throw std::range_error();
		}
	
		TREE& push_front(TREE* t)
		{
			if (t->_parent)
			{
				throw std::runtime_error("invalid parent");
			}
			t->_parent = static_cast<TREE*>(this);
			if (_child)
			{
				_child->_prev = t; t->_next = _child;
			}
			else
			{
				_end = t;
			}
			_child = t;
			return *t;
		}
	
		TREE& push_back(TREE* t)
		{
			if (t->_parent)
			{
				throw std::runtime_error("invalid parent");
			}
			t->_parent = static_cast<TREE*>(this);
			if (_end)
			{
				_end->_next = t; t->_prev = _end;
			}
			else
			{
				_child = t;
			}
			_end = t;
			return *t;
		}
	
		virtual ~basic_tree()
		{
			TREE* c = _child;
			while (c)
			{
				TREE* n = c->_next;
				delete c;
				c = n;
			}
		}
	
		typedef basic_iterator<TREE> iterator;
		typedef basic_const_iterator<TREE> const_iterator;
	
		iterator begin()
		{
			return iterator(_child);
		}
		const_iterator begin() const
		{
			return const_iterator(_child);
		}
	
		iterator end()
		{
			return iterator(0);
		}
		const_iterator end() const
		{
			return const_iterator(0);
		}
	
	};
	
	template <typename ITERATOR, typename FUNC>
	void for_each_iter(const ITERATOR& t, FUNC& f, int depth = 0)
	{
		f(t, depth);
		ITERATOR i = (*t).begin();
		ITERATOR end = (*t).end();
		for (; i != end; ++i)
		{
			for_each_iter(i, f, depth + 1);
		}
	}

	template <typename ITERATOR, typename FIN, typename FOUT>
	void for_each_iter(const ITERATOR& t, FIN& fin, FOUT& fout, int depth = 0)
	{
		fin(t, depth);
		ITERATOR i = (*t).begin(); ITERATOR end = (*t).end();
		for (; i != end; ++i)
		{
			for_each_depth(i, fin, fout, depth + 1);
		}
		fout(t, depth);
	}

	template <typename ITERATOR, typename FIN, typename FOUT, typename FEMPTY>
	void for_each_iter(const ITERATOR& t, FIN& fin, FOUT& fout, FEMPTY& fempty, int depth = 0)
	{
		if (t.empty())
		{
			fempty(t, depth);
		}
		else
		{
			fin(t, depth);
			ITERATOR i = (*t).begin(); ITERATOR end = (*t).end();
			for (; i != end; ++i)
			{
				for_each_depth(i, fin, fout, fempty, depth + 1);
			}
			fout(t, depth);
		}
	}
	
	
	/** A tree container class
	This class implements a container-like tree class. It stores a TYPE payload at each 
	node. It derives from the basic_tree template to implement the tree-like structure,
	and adds overloaded methods to directly add/remove TYPE data to the tree.
	A dereferencing operator is provided, as are overloaded iterator classes.
	
	\note This class serves as a basic example of how to specialise the basic_tree
	template to build a new tree-like structure.
	*/
	template <typename TYPE>
	struct tree
	: basic_tree< tree<TYPE> >
	{
		typedef basic_tree< tree<TYPE> > base_tree;
	
		TYPE _payload;
	
		/*
		typedef TYPE value_type;
		typedef TYPE* pointer;
		typedef TYPE& reference;
		typedef const TYPE& const_reference;
		typedef unsigned int size_type;
		typedef int difference_type;
		*/
	
		tree(const TYPE& payload = TYPE())
		: _payload(payload)
		{}
	
		TYPE& operator*()
		{
			return _payload;
		}
		const TYPE& operator*() const
		{
			return _payload;
		}
	
		tree& push_front(const TYPE& payload = TYPE())
		{
			tree* t = new tree(payload);
			basic_tree< tree<TYPE> >::push_front(t);
			return *t;
		}
		tree& push_back(const TYPE& payload = TYPE())
		{
			tree* t = new tree(payload);
			basic_tree< tree<TYPE> >::push_back(t);
			return *t;
		}
	
		typedef typename basic_tree< tree<TYPE> >::iterator base_iterator;
		struct iterator
		: base_iterator
		{
			explicit iterator(tree* tree_in)
			: base_iterator(tree_in)
			{}
		
			iterator push_front(const TYPE& payload = TYPE())
			{
				iterator result(&(this->_tree->push_front(payload)));
				return result;
			}
			iterator push_back(const TYPE& payload = TYPE())
			{
				iterator result(&(this->_tree->push_back(payload)));
				return result;
			}
		};
		typedef typename basic_tree< tree<TYPE> >::const_iterator base_const_iterator;
		struct const_iterator
		: base_const_iterator
		{
			explicit const_iterator(const tree* tree_in)
			: base_const_iterator(tree_in)
			{}
		};
	
		iterator begin()
		{
			return iterator(this->_child);
		}
		const_iterator begin() const
		{
			return const_iterator(this->_child);
		}
		iterator end()
		{
			return iterator(0);
		}
		const_iterator end() const
		{
			return const_iterator(0);
		}
	
	};

	template <typename TYPE, typename FUNC>
	void for_each_depth(tree<TYPE>& t, FUNC& f, int depth = 0)
	{
		f(*t, depth);
		typename tree<TYPE>::iterator i = t.begin();
		typename tree<TYPE>::iterator end = t.end();
		for (; i != end; ++i)
		{
			for_each_depth(*i, f, depth + 1);
		}
	}

	template <typename TYPE, typename FUNC>
	void for_each_depth(const tree<TYPE>& t, FUNC& f, int depth = 0)
	{
		f(*t, depth);
		typename tree<TYPE>::const_iterator i = t.begin();
		typename tree<TYPE>::const_iterator end = t.end();
		for (; i != end; ++i)
		{
			for_each_depth(*i, f, depth + 1);
		}
	}



	template <typename TYPE, typename FIN, typename FOUT>
	void for_each_depth(tree<TYPE>& t, FIN& fin, FOUT& fout, int depth = 0)
	{
		fin(*t, depth);
		typename tree<TYPE>::iterator i = t.begin();
		typename tree<TYPE>::iterator end = t.end();
		for (; i != end; ++i)
		{
			for_each_depth(*i, fin, fout, depth + 1);
		}
		fout(*t, depth);
	}

	template <typename TYPE, typename FIN, typename FOUT>
	void for_each_depth(const tree<TYPE>& t, FIN& fin, FOUT& fout, int depth = 0)
	{
		fin(*t, depth);
		typename tree<TYPE>::const_iterator i = t.begin();
		typename tree<TYPE>::const_iterator end = t.end();
		for (; i != end; ++i)
		{
			for_each_depth(*i, fin, fout, depth + 1);
		}
		fout(*t, depth);
	}



	template <typename TYPE, typename FIN, typename FOUT, typename FEMPTY>
	void for_each_depth(tree<TYPE>& t, FIN& fin, FOUT& fout, FEMPTY& fempty, int depth = 0)
	{
		if (t.empty())
		{
			fempty(*t, depth);
		}
		else
		{
			fin(*t, depth);
			typename tree<TYPE>::iterator i = t.begin();
			typename tree<TYPE>::iterator end = t.end();
			for (; i != end; ++i)
			{
				for_each_depth(*i, fin, fout, fempty, depth + 1);
			}
			fout(*t, depth);
		}
	}

	template <typename TYPE, typename FIN, typename FOUT, typename FEMPTY>
	void for_each_depth(const tree<TYPE>& t, FIN& fin, FOUT& fout, FEMPTY& fempty, int depth = 0)
	{
		if (t.empty())
		{
			fempty(*t, depth);
		}
		else
		{
			fin(*t, depth);
			typename tree<TYPE>::const_iterator i = t.begin();
			typename tree<TYPE>::const_iterator end = t.end();
			for (; i != end; ++i)
			{
				for_each_depth(*i, fin, fout, fempty, depth + 1);
			}
			fout(*t, depth);
		}
	}




}

#endif









